package com.dyz.leetcode._19_greedy;

public class _134_canCompleteCircuit {
    public int canCompleteCircuit1(int[] gas, int[] cost) {

        for(int i=0; i<gas.length; i++){
            if(gas[i]<cost[i]){continue;}
            int index = i;
            int remianGas = gas[i] - cost[i];
            while(remianGas>=0){
                index = (index+1)%gas.length;
                if(index == i){return i;}
                remianGas = remianGas - cost[index]+gas[index];
            }
        }
        return -1;
    }
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;

        int totalGas = 0; // 总油量
        int currGas = 0; // 当前总油量
        int startStation = 0;
        for (int i = 0; i < n; i++) {
            totalGas += gas[i] - cost[i];
            currGas += gas[i] - cost[i];
            if (currGas < 0) {
                startStation = i + 1;
                currGas = 0;
            }
        }

        return totalGas >= 0 ? startStation : -1;
    }
}
